#leetcode题目74：搜索二维矩阵
#难度：中等

#方法：二分查找

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        i, j = 0, m * n - 1
        while i <= j:
            mid = i + (j - i) // 2
            x = mid // n
            y = mid % n
            if matrix[x][y] == target:
                return True
            elif matrix[x][y] > target:
                j = mid - 1
            else:
                i = mid + 1
        return False


#测试数据
matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]]
target=3
#预期输出：True
solution=Solution()
print(solution.searchMatrix(matrix,target))

matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]]
target=13
#预期输出：False
solution=Solution()
print(solution.searchMatrix(matrix,target))

matrix=[[1]]
target=1
#预期输出：True
solution=Solution()
print(solution.searchMatrix(matrix,target))
        
        